10-701 Introduction to Machine Learning (PhD)
Lecture 1: Intro to ML and Perceptron
Lecture 1: Intro to ML and Perceptron
Leila Wehbe
Carnegie Mellon University
Machine Learning Department
Carnegie Mellon University
Machine Learning Department
Lecture based on material from Tom Mitchell's lecture 2, Nina Balcan's lecture 2, and on on Kilian Weinberger's lecture 17
Lecture outcomes¶
- What is a decision tree
- How to use information gain as a heuristic to building a short tree
- Notion of overfitting
Links (use the version you need)¶
First we will finish the proof from last lecture¶
The Perceptron¶
- Assume data is binary
- Assume data is linearly separable:
- there exist a hyperplane that perfectly divides the two classes \begin{align}\exists {\bf w},b ~ ~ \text{ s.t. } ~ ~ \forall({\bf x}_i,y_i) \in D,\\ y_i({\bf w}^\top {\bf x}_i +b)>0 \end{align}
Convergence of the perceptron algorithm¶
The perceptron algorithm converges in $\frac{1}{\gamma^2}$ updates if the data is linearly separable.
$\gamma$ is the margin of the problem instance (defined on next slide).
Notion of Margin¶
- Assume there exists ${\bf w}^*$ such that $ ~ ~ \forall({\bf x_i},y_i) \in D$, $ ~ ~ ~ y_i({\bf x_i}^\top {\bf w}^*)>0$
- Also assume we rescale ${\bf w}^*$ and ${\bf x_i}$s such that:
- $||{\bf w}^*||=1 ~ ~ ~ $ and $~ ~ ~ ||{\bf x_i}||\le1 ~ ~ \forall {\bf x_i} $ $~~~~~$(how?)
- The margin $\gamma$ of the hyperplane ${\bf w}^*$ is the minimum distance between one
of the points and the hyperplane:
- $\gamma = \min_{({\bf x_i},y_i)\in \mathcal{D}} |{\bf x_i}^\top {\bf w}^*|$ $~~~~~$(since ${\bf w}^*$ is unit norm)
source
- $\gamma = \min_{({\bf x_i},y_i)\in \mathcal{D}} |{\bf x_i}^\top {\bf w}^*|$ $~~~~~$(since ${\bf w}^*$ is unit norm)
Theorem¶
Given:
- All ${\bf x}_i$s are within the unit sphere
- There exists a separating hyperplane ${\bf w}^*$, with $||{\bf w}^*||=1$
- $\gamma$ is the margin of hyperplane ${\bf w}^*$
If all of the above holds, then the Perceptron algorithm makes at most $\frac{1}{\gamma^2}$ mistakes.
- Would we want a large margin or a small margin?
- What types of datasets will converge quickly?
- What happens if the data is not separable?
- Does the order matter?
Function approximation¶
Problem setting:¶
- Set of possible instances $X$
- Unknown target function $f:X\rightarrow Y$
- Set of candidate hypotheses $H={h | h:X\rightarrow Y}$
Input:¶
- Training examples $\langle x^{(i)},y^{(i)} \rangle$ of unknown target function $f$
Output:¶
- Hypothesis $h \in H$ that best approximates target function $f$
Decision trees¶
Learn concept PlayTennis (i.e., decide whether our friend will play tennis in a given day)
PLAY TENNIS?¶
- A Decision tree for $f$: (Outlook, Temperature, Humidity, Wind) $\rightarrow$ PlayTennis?
- Each internal node: test one discrete-valued attribute $X_d$
- Each branch from a node: selects one value for $X_d$
- Each leaf node: predict $Y$ (or $P(Y | X \in \text{leaf})$)
Example: x=(Outlook=sunny, Temperature-Hot, Humidity=Normal,Wind=High), h(x)=Yes
Decision tree example¶
Suppose $X = (X_1,X_2,… X_n)$ where $X_i$ are boolean-valued variables
How would you represent $Y = X2\land X5?$ $~ ~ ~ ~ ~ $ $Y = X2\lor X5?$
How would you represent $X_2X_5\lor X_3X_4(\neg X1)?$
Example with training data¶
| $$X_1$$ | $$X_2$$ | $$X_3$$ | $$Y$$ | |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 1 | |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 |
- The order we pick the attributes affects the size (and efficiency) of the tree.
How to choose the best hypothesis?¶
How to automatically find a good hypothesis for training data?
- A core algorithmic question.
When do we generalize and do well on unseen data?
- A learning theory question.
- Occam’s razor: use the simplest hypothesis consistent with data!
- Occam’s razor: Fewer short hypotheses than long ones
- a short hypothesis that fits the data is less likely to be a statistical coincidence
- highly probable that a sufficiently complex hypothesis will fit the data
- (remember this is a heuristic. read here for more discussion)
How to choose the best hypothesis?¶
How to automatically find a good hypothesis for training data?
- A core algorithmic question.
When do we generalize and do well on unseen data?
- A learning theory question.
- Occam’s razor: use the simplest hypothesis consistent with data!
Other core questions in machine learning:
- How do we choose a hypothesis space?
- Often we use prior knowledge to guide this choice
- How to model applications as machine learning problems?
- engineering challenge
- How do we choose a hypothesis space?
How to choose the best Decision Tree?¶
How to pick the smallest tree?
- NP-hard [Hyafil-Rivest’76]!
Luckily, we have very nice practical heuristics and top down algorithms (e.g, ID3) that can achieve a good solution
Top-Down Induction of Decision Trees [examples ID3, C4.5, Quinlan]¶
ID3: Natural greedy approach to growing a decision tree top-down (from the root to the leaves by repeatedly replacing an existing leaf with an internal node.).
Algorithm main loop:
- Pick “best” attribute A to split at a node based on training data.
- Assign A to this node.
- For each value of A create new descendent.
- Split training examples among the descendents.
- If training examples perfectly classified in new node, stop, else recurse on node.
- How to know which attribute is best?
Which attribute is best?¶
- ID3 uses a statistical measure called information gain (how well a given attribute separates the training examples according to the target classification)
- Information Gain of variable $A$ is the expected reduction in entropy of target variable $Y$ for data sample $S4$, due to sorting on variable $A$
- Entropy ($H_S$) is information theoretic measure that characterizes the complexity of a labeled set 𝑆.
Entropy¶
- Sample Entropy of a Labeled Dataset
- $𝑆$ is a sample of training examples
- $p_1$ is the proportion of positive examples in $𝑆$
- $p_0$ the proportion of negative examples in $𝑆$
- $𝑆$ is a sample of training examples
• Entropy measures the complexity of 𝑆:
$$H_S = - p_1 \log(p_1) - p_0 \log(p_0)$$
Entropy¶
$$H_S = - p_1 \log(p_1) - p_0 \log(p_0)$$
- E.g., if all negative, then entropy=0. If all positive, then entropy=0.
- If 50/50 positive and negative then entropy=1.
- If 14 examples with 9 positive and 5 negative, then entropy=.940
If labels not Boolean¶
$$H_S = - \sum_{k=1}^c p_k \log_2(p_k)$$E.g., if $c$ classes, all equally likely, then $p_k= \frac{1}{c}$ for all $k$ and $H_S = -\log_2$
Another way to understand maximizing information gain¶
We want to be the farthest possible from all classes being equally likely (let's call this uniform distribution $q_k= \frac{1}{c}$ for all $k$). This can be done by finding another distribution $(p_1,...p_c)$ that maximizes the KL-Divergence (Kullback–Leibler divergence).
The KL-Divergence is not a metric because it is not symmetric, i.e., $\text{KL}(p||q)\ne \text{KL}(q||p)$.)
Entropy of a split¶
- if binary:
- more generallly for $c$ classes:
Information gain of a split¶
- Information Gain of variable $A$ is the expected reduction in entropy of target variable $Y$ for data sample $S4$, due to sorting on variable $A$ (with $c$ values):
- Gain(S,A) is the information provided about the target function, given the value of some other attribute A.
Learn concept PlayTennis (i.e., decide whether our friend will play tennis in a given day)
Final decision tree¶
Properties of ID3¶
- ID3 performs heuristic search through space of decision trees.
- It stops at smallest acceptable tree. (Occam's razor).
- Still a greedy approach, might not find the shortest tree.
ID3 might still overfit!¶
Overfitting could occur because of noisy data and because ID3 is not guaranteed to output a small hypothesis even if one exists.
Consider adding a noisy example:
- Sunny, Hot, Normal, Strong, PlayTennis = No
The tree we learned would not be compatible with the training data
Overfitting¶
- Consider a hypothesis h and its
- Error rate over training data: $errortrain(h)$
- True error rate over all data: $errortrue(h)$
- We say h overfits the training data if $errortrue(h) > errortrain(h)$
- We typically don't know $errortrue(h)$ but we can estimate $errortest(h)$ on a heldout set from the same distribution as the training data.
- Amount of overfitting = $errortrue(h)-errortrain(h)$
Example of overfitting in ID3¶
Task: learning which medical patients have a form of diabetes.
How can we avoid overfitting?¶
- Stop growing when data split not statistically significant
Grow full tree, then prune it
example: Reduced Error Pruning
- Split data into training set and validation set
- Train a tree to classify training set as well as possible
- Do until further pruning is harmful:
- For each internal tree node, consider making it a leaf node (pruning the tree below it)
- Greedily chose the above pruning step that best improves error over validation set
- Produces smallest version of the most accurate pruned tree
What if my attributes $X$ are real valued?¶
- Use a decision stump: for each attribute, consider splitting above, below
- e.g. (is Temperature $\ge$ 72)
Ensemble learning, bagging¶
- Using ensemble learning with trees makes them work very well in practice
- instead of one tree, create a forest of trees and combine their prediction
- Bagging: resample the training dataset with replacement and average the trees
Random forests: use subsets of the data (different features)
Will see ensemble learning later in the couse